\documentclass[a4paper,11pt]{article}
%
% HOW TO USE THIS TEMPLATE:
%
% IN THE TWO INDICATED PLACES BELOW,
%   ENTER YOUR NAMES AND THE NUMBER OF THE HOMEWORK
%
% FOR EACH PROBLEM IN THE SET, WRITE YOUR SOLUTION IN A FILE
%   NAMED "Problem1.tex", "Problem2.tex", etc.
%   THESE SOLUTIONS FILES HAVE NO PREAMBLE (\documentclass,
%   \usepackage, etc) ANDNO \begin{document} \end{document}
%   (THEY JUST GET INLINED WHEN RUNNING LaTeX)
%
% THIS FILE IS SET UP FOR 4 PROBLEMS, SO COMMENT OUT OR
%   UNCOMMENT PROBLEM BLOCKS (AT END OF FILE) AS NECESSARY.
%
% PLACE THESE SOLUTIONS FILES AND THE TEMPLATE IN THE SAME DIRECTORY
%
% RUN LaTeX-LaTeX-dvips-psp2df, or run pdfLaTeX, or run whatever chain
%   you normally use
%
% IF YOU NEED TO ADD PACKAGES (E.G., FOR HANDLING FIGURES, OR
%   FOR RUNNING PDFLaTeX), , UNCOMMENT LINE BELOW AND ENTER THE PACKAGE NAMES
%  \usepackage{additional_package_1,additional_package_2}

%%%% NOTE: IF YOUR LAST NAME HAS ACCENTS, SOME LaTeX COMMANDS ARE:
%%%%       for diaeresis/umlaut ", as in German, use \"a, \"u, \"o, etc.
%%%%       for grave accent `, use \`e, \`a, \`u
%%%%       for acute accent ', use \'a, \'e, \'u
%%%%       for tilde ~, use \tilde{a}, \tilde{o}
%%%%       for caret ^, use \hat{e}, \hat{o}
%%%%	   if you need an accent on an i, say an umlaut, use \"\i{}
%%%%		the \i{} is an i without its dot; e.g., na\"\i{}ve
%%%%	   these all work well with lower-case letters,
%%%%	        but only so-so with upper-case letters
%%%%
%%%% REPLACE Doe, Smith, and Wilson WITH YOUR LAST NAMES
  \def\myname{Sintsova, Trigonakis, and Picorel}
%%%% REPLACE xxx WITH CORRECT HOMEWORK NUMBER
  \def\mynumber{005}



% DO NOT MODIFY THIS NEXT PART
%%%%%
  \usepackage{times,amsmath,pslatex,graphicx}
  \newcounter{problem}
  \setcounter{problem}{0}
  \makeatletter
  \def\ps@headings{%
    \let\@mkboth\markboth
    %\def\@evenfoot{\hfil\large\sf Homework \mynumber, Problem \theproblem\hfil}
    \def\@oddfoot{\@evenfoot}
    \def\@evenhead{\large\sc\myname\hfil\it\today\hfil\sf P.~\thepage}
    \def\@oddhead{\@evenhead}}
  \makeatother
  \pagestyle{headings}
  \advance\textwidth by16mm
  \advance\oddsidemargin by-8mm
  \advance\textheight by10mm
  
  \usepackage{amsmath}
  \usepackage{amsfonts}
  \usepackage{amssymb}
  \usepackage{makeidx}
  \usepackage{listings}
  \usepackage{graphicx}
  \usepackage{tikz}
  
  \lstset{
  	basicstyle=\ttfamily,
  	commentstyle=\color{gray},
  	stringstyle=\color{dkgreen},
  	numbers=left,
  	numberstyle=\footnotesize\color{gray},
  	numbersep=8pt,
  	backgroundcolor=\color{white},
  	breaklines=true
  }
%%%%%

\begin{document}

1. Given a directed graph G and two vertices $s$ and $t$, use a max-flow solver to compute the maximum number of edge-disjoint $s-t$ paths. Can you extend your approach to compute the maximum number of vertex-disjoint $s-t$ paths? \\

\textbf{Edge-disjoint paths}\\

In order to calculate the maximum number of edge-disjoint paths we have to assign to all edges the capacity of one. By doing this we assure that the number of augmenting paths across any edge is at most one. This is true because only one augmenting path from $s$ to $t$ will traverse the same edges. After running the maxflow algorithm, the number of edge-disjoint paths will be equal to the maxflow because each augmenting path will traverse a flow of value one so the number of edge disjoint paths will be equal to the number of augmenting paths (which are edge-disjoint since the edges have capacity one).\\

\textbf{Vertex-disjoint paths}\\

One easy solution is to transform every vertex into two vertices in order to define a directed edge. Lets say that we have some edges pointing to a vertex and others coming out. By converting the single vertex into a two vertices like in the following picture:

\begin{center}
\includegraphics[scale=0.5]{get-cut-2.png}  
\end{center}

This will allow us to apply the same idea as in the first solution. Since all the capacities will be one, the number of edge-disjoint paths will be equal to the maximum flow. But in our case, since we have transformed each vertex into an edge, we assure that the number of vertex-disjoint paths is defined by the number of edge-disjoint paths. This is true because no two augmenting paths will traverse the same vertex.\\

3. Give a proof or a counterexample for each of the following two assertions:

\begin{enumerate}
\item[a)] For a flow network with integer capacities, if all edge capacities are even, then there exists a maximum $s-t$ flow such that the amount of flow o each edge is even.
\item[b)] For a flow network with integer capacities, if all edge capacities are odd, then there exists a maximum $s-t$ flow such that the amount of flow on each edge is odd.
\end{enumerate}

\subparagraph{a)}

Because in a graph $G=(V,E)$ the maximum flow is equal to the minimum cut lets have a generic minimum cut:

\begin{center}
\includegraphics[scale=0.5]{gen-cut.png}
\end{center} 

The value of the maximum flow and the aggregate capacity of the cut (minumun) is:\\

$c(e_{1})+c(e_{2})+...+c(e_{n})$\\

Because all the capacities of the edges are even we know that: \\

$c(e_{1})+c(e_{2})+...+c(e_{n}) = 2k_{1}+2k_{2}+...+2k_{n}=2(k_{1}+...+k_{n})$ \\

The amount of maximum flow is even. We can assure that it exits at least one of the following two ways to construct the residual graph: 

\subparagraph{One augmenting path} We assure that the amount of flow on each of the edges is equal to the maxflow so since the maxflow is even it will be even.

\subparagraph{More than one augmenting path} If we have more than one augmenting paths in the edges of the graph we will have $2K_{i}$ flow or any combination of them if more than one augmenting path traverse through that edge. Since the capacities of the minimum cut are even, we know that any combination of flows created by the maximum capacity of the edges that are in the minimum cut, will be also even if the capacity of the edge is higher that amount of flow. On the other hand, if the edge is limiting the amount of flow of the augmenting path, because we know that the capacity of the edge is even and is going to be saturated we assure that the flow is even.

\subparagraph{b)} 

This is not true, because if maxflow is even and all this amount have to go through one edge with higher capacity than the value of the maxflow, this will produce an even flow traversing through that edge. The maxflow is even in case the min-cut contains even number of edges, as all of them have odd capacities saturated. In other words, since all of the capacities are odd, if even number of augmenting paths goes through an edge (each of them with an odd flow, as defined by the edge with the minimum capacity), then the flow in that edge will be even.

\begin{flushleft}
Lets draw a counterexample:
\end{flushleft}

\begin{center}
\includegraphics[scale=0.5]{odd-cut.png} 
\end{center}

We see that in the first edge which begins in the sink which has an odd capacity there is an even amount of flow traversing this edge because there is a even number of augmenting paths going through that edge. Which means that any even combination of flows defined by the minimum cut that traverse an edge of higher capacity will make a even amount of flow.







 
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \newpage
% \begin{flushleft}
%   \addtocounter{problem}{1}
%   \large\sf Problem \theproblem .
% \end{flushleft}
% 
% \input{problem5.tex}
% 

\end{document}
